/*
Date:20220305 17:07PM
key:二分查找找到路径，从后往前看路径重合点。
 */
class Solution {
public:
    void mid(TreeNode* root,vector<TreeNode*>&v,TreeNode* p)
    {
        v.push_back(root);
        if(root==p){return;}
        if(p->val> root->val)
        {

            mid(root->right,v, p);
        }else
        {
            mid(root->left,v, p);
        }
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        vector<TreeNode*>v,v1;
        mid(root,v,p);
        mid(root,v1,q);
        set<TreeNode*>s(v.begin(),v.end());
        for(int i=v1.size()-1;i>-1;i--)
        {
            if(s.count(v1[i])==1)
            {
                return v1[i];
            }
        }
        return root;
    }
};